Search Results

Documents authored by Löffler, Maarten

Document
DOI: 10.4230/DagRep.13.5.165
Computational Geometry (Dagstuhl Seminar 23221)

Authors: Siu-Wing Cheng, Maarten Löffler, Jeff M. Phillips, and Aleksandr Popov

Published in: Dagstuhl Reports, Volume 13, Issue 5 (2023)

Abstract
This report documents the program and the outcomes of the Dagstuhl Seminar 23221 "Computational Geometry". The seminar was held from May 29th to June 2nd, 2023, and 39 participants from various countries attended it, including two remote participants. Recent advances in computational geometry were presented and discussed, and new challenges were identified. This report collects the abstracts of the talks and the open problems presented at the seminar.
Cite as

Siu-Wing Cheng, Maarten Löffler, Jeff M. Phillips, and Aleksandr Popov. Computational Geometry (Dagstuhl Seminar 23221). In Dagstuhl Reports, Volume 13, Issue 5, pp. 165-181, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.13.5.165,
  author =	{Cheng, Siu-Wing and L\"{o}ffler, Maarten and Phillips, Jeff M. and Popov, Aleksandr},
  title =	{{Computational Geometry (Dagstuhl Seminar 23221)}},
  pages =	{165--181},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{5},
  editor =	{Cheng, Siu-Wing and L\"{o}ffler, Maarten and Phillips, Jeff M. and Popov, Aleksandr},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.13.5.165},
  URN =		{urn:nbn:de:0030-drops-193692},
  doi =		{10.4230/DagRep.13.5.165},
  annote =	{Keywords: Algorithms, Combinatorics, Geometric Computing, Reconfiguration, Uncertainty}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.48
Shortest Paths in Portalgons

Authors: Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.
Cite as

Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals. Shortest Paths in Portalgons. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.SoCG.2023.48,
  author =	{L\"{o}ffler, Maarten and Ophelders, Tim and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Shortest Paths in Portalgons}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.48},
  URN =		{urn:nbn:de:0030-drops-178980},
  doi =		{10.4230/LIPIcs.SoCG.2023.48},
  annote =	{Keywords: Polyhedral surfaces, shortest paths, geodesic distance, Delaunay triangulation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.34
Minimum Link Fencing

Authors: Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We study a variant of the geometric multicut problem, where we are given a set 𝒫 of colored and pairwise interior-disjoint polygons in the plane. The objective is to compute a set of simple closed polygon boundaries (fences) that separate the polygons in such a way that any two polygons that are enclosed by the same fence have the same color, and the total number of links of all fences is minimized. We call this the minimum link fencing (MLF) problem and consider the natural case of bounded minimum link fencing (BMLF), where 𝒫 contains a polygon Q that is unbounded in all directions and can be seen as an outer polygon. We show that BMLF is NP-hard in general and that it is XP-time solvable when each fence contains at most two polygons and the number of segments per fence is the parameter. Finally, we present an O(n log n)-time algorithm for the case that the convex hull of 𝒫⧵{Q} does not intersect Q.
Cite as

Sujoy Bhore, Fabian Klute, Maarten Löffler, Martin Nöllenburg, Soeren Terziadis, and Anaïs Villedieu. Minimum Link Fencing. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2022.34,
  author =	{Bhore, Sujoy and Klute, Fabian and L\"{o}ffler, Maarten and N\"{o}llenburg, Martin and Terziadis, Soeren and Villedieu, Ana\"{i}s},
  title =	{{Minimum Link Fencing}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.34},
  URN =		{urn:nbn:de:0030-drops-173191},
  doi =		{10.4230/LIPIcs.ISAAC.2022.34},
  annote =	{Keywords: computational geometry, polygon nesting, polygon separation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.58
Segment Visibility Counting Queries in Polygons

Authors: Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
Let P be a simple polygon with n vertices, and let A be a set of m points or line segments inside P. We develop data structures that can efficiently count the objects from A that are visible to a query point or a query segment. Our main aim is to obtain fast, O(polylog nm), query times, while using as little space as possible. In case the query is a single point, a simple visibility-polygon-based solution achieves O(log nm) query time using O(nm²) space. In case A also contains only points, we present a smaller, O(n + m^{2+ε} log n)-space, data structure based on a hierarchical decomposition of the polygon. Building on these results, we tackle the case where the query is a line segment and A contains only points. The main complication here is that the segment may intersect multiple regions of the polygon decomposition, and that a point may see multiple such pieces. Despite these issues, we show how to achieve O(log n log nm) query time using only O(nm^{2+ε} + n²) space. Finally, we show that we can even handle the case where the objects in A are segments with the same bounds.
Cite as

Kevin Buchin, Bram Custers, Ivor van der Hoog, Maarten Löffler, Aleksandr Popov, Marcel Roeloffzen, and Frank Staals. Segment Visibility Counting Queries in Polygons. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ISAAC.2022.58,
  author =	{Buchin, Kevin and Custers, Bram and van der Hoog, Ivor and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel and Staals, Frank},
  title =	{{Segment Visibility Counting Queries in Polygons}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.58},
  URN =		{urn:nbn:de:0030-drops-173431},
  doi =		{10.4230/LIPIcs.ISAAC.2022.58},
  annote =	{Keywords: Visibility, Data Structure, Polygons, Complexity}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.67
Chromatic k-Nearest Neighbor Queries

Authors: Thijs van der Horst, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Let P be a set of n colored points. We develop efficient data structures that store P and can answer chromatic k-nearest neighbor (k-NN) queries. Such a query consists of a query point q and a number k, and asks for the color that appears most frequently among the k points in P closest to q. Answering such queries efficiently is the key to obtain fast k-NN classifiers. Our main aim is to obtain query times that are independent of k while using near-linear space. We show that this is possible using a combination of two data structures. The first data structure allow us to compute a region containing exactly the k-nearest neighbors of a query point q, and the second data structure can then report the most frequent color in such a region. This leads to linear space data structures with query times of O(n^{1/2} log n) for points in ℝ¹, and with query times varying between O(n^{2/3}log^{2/3} n) and O(n^{5/6} polylog n), depending on the distance measure used, for points in ℝ². These results can be extended to work in higher dimensions as well. Since the query times are still fairly large we also consider approximations. If we are allowed to report a color that appears at least (1-ε)f^* times, where f^* is the frequency of the most frequent color, we obtain a query time of O(log n + log log_{1/(1-ε)} n) in ℝ¹ and expected query times ranging between Õ(n^{1/2}ε^{-3/2}) and Õ(n^{1/2}ε^{-5/2}) in ℝ² using near-linear space (ignoring polylogarithmic factors).
Cite as

Thijs van der Horst, Maarten Löffler, and Frank Staals. Chromatic k-Nearest Neighbor Queries. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.ESA.2022.67,
  author =	{van der Horst, Thijs and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Chromatic k-Nearest Neighbor Queries}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.67},
  URN =		{urn:nbn:de:0030-drops-170055},
  doi =		{10.4230/LIPIcs.ESA.2022.67},
  annote =	{Keywords: data structure, nearest neighbor, classification}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.21
Nearest-Neighbor Decompositions of Drawings

Authors: Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer, and Daniel Perz

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
Let 𝒟 be a set of straight-line segments in the plane, potentially crossing, and let c be a positive integer. We denote by P the union of the endpoints of the straight-line segments of 𝒟 and of the intersection points between pairs of segments. We say that 𝒟 has a nearest-neighbor decomposition into c parts if we can partition P into c point sets P₁, … , P_c such that 𝒟 is the union of the nearest neighbor graphs on P₁, … , P_c. We show that it is NP-complete to decide whether 𝒟 can be drawn as the union of c ≥ 3 nearest-neighbor graphs, even when no two segments cross. We show that for c = 2, it is NP-complete in the general setting and polynomial-time solvable when no two segments cross. We show the existence of an O(log n)-approximation algorithm running in subexponential time for partitioning 𝒟 into a minimum number of nearest-neighbor graphs. As a main tool in our analysis, we establish the notion of the conflict graph for a drawing 𝒟. The vertices of the conflict graph are the connected components of 𝒟, with the assumption that each connected component is the nearest neighbor graph of its vertices, and there is an edge between two components U and V if and only if the nearest neighbor graph of U ∪ V contains an edge between a vertex in U and a vertex in V. We show that string graphs are conflict graphs of certain planar drawings. For planar graphs and complete k-partite graphs, we give additional, more efficient constructions. We furthermore show that there are subdivisions of non-planar graphs that are not conflict graphs. Lastly, we show a separator lemma for conflict graphs.
Cite as

Jonas Cleve, Nicolas Grelier, Kristin Knorr, Maarten Löffler, Wolfgang Mulzer, and Daniel Perz. Nearest-Neighbor Decompositions of Drawings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cleve_et_al:LIPIcs.SWAT.2022.21,
  author =	{Cleve, Jonas and Grelier, Nicolas and Knorr, Kristin and L\"{o}ffler, Maarten and Mulzer, Wolfgang and Perz, Daniel},
  title =	{{Nearest-Neighbor Decompositions of Drawings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{21:1--21:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.21},
  URN =		{urn:nbn:de:0030-drops-161812},
  doi =		{10.4230/LIPIcs.SWAT.2022.21},
  annote =	{Keywords: nearest-neighbors, decompositions, drawing}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.2
On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem

Authors: Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We consider the following surveillance problem: Given a set P of n sites in a metric space and a set R of k robots with the same maximum speed, compute a patrol schedule of minimum latency for the robots. Here a patrol schedule specifies for each robot an infinite sequence of sites to visit (in the given order) and the latency L of a schedule is the maximum latency of any site, where the latency of a site s is the supremum of the lengths of the time intervals between consecutive visits to s. When k = 1 the problem is equivalent to the travelling salesman problem (TSP) and thus it is NP-hard. For k ≥ 2 (which is the version we are interested in) the problem becomes even more challenging; for example, it is not even clear if the decision version of the problem is decidable, in particular in the Euclidean case. We have two main results. We consider cyclic solutions in which the set of sites must be partitioned into 𝓁 groups, for some 𝓁 ≤ k, and each group is assigned a subset of the robots that move along the travelling salesman tour of the group at equal distance from each other. Our first main result is that approximating the optimal latency of the class of cyclic solutions can be reduced to approximating the optimal travelling salesman tour on some input, with only a 1+ε factor loss in the approximation factor and an O((k/ε) ^k) factor loss in the runtime, for any ε > 0. Our second main result shows that an optimal cyclic solution is a 2(1-1/k)-approximation of the overall optimal solution. Note that for k = 2 this implies that an optimal cyclic solution is optimal overall. We conjecture that this is true for k ≥ 3 as well. The results have a number of consequences. For the Euclidean version of the problem, for instance, combining our results with known results on Euclidean TSP, yields a PTAS for approximating an optimal cyclic solution, and it yields a (2(1-1/k)+ε)-approximation of the optimal unrestricted (not necessarily cyclic) solution. If the conjecture mentioned above is true, then our algorithm is actually a PTAS for the general problem in the Euclidean setting. Similar results can be obtained by combining our results with other known TSP algorithms in non-Euclidean metrics.
Cite as

Peyman Afshani, Mark de Berg, Kevin Buchin, Jie Gao, Maarten Löffler, Amir Nayyeri, Benjamin Raichel, Rik Sarkar, Haotian Wang, and Hao-Tsung Yang. On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.SoCG.2022.2,
  author =	{Afshani, Peyman and de Berg, Mark and Buchin, Kevin and Gao, Jie and L\"{o}ffler, Maarten and Nayyeri, Amir and Raichel, Benjamin and Sarkar, Rik and Wang, Haotian and Yang, Hao-Tsung},
  title =	{{On Cyclic Solutions to the Min-Max Latency Multi-Robot Patrolling Problem}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{2:1--2:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.2},
  URN =		{urn:nbn:de:0030-drops-160109},
  doi =		{10.4230/LIPIcs.SoCG.2022.2},
  annote =	{Keywords: Approximation, Motion Planning, Scheduling}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.1
Pushing Blocks by Sweeping Lines

Authors: Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
We investigate the reconfiguration of n blocks, or "tokens", in the square grid using line pushes. A line push is performed from one of the four cardinal directions and pushes all tokens that are maximum in that direction to the opposite direction by one unit. Tokens that are in the way of other tokens are displaced in the same direction, as well. Similar models of manipulating objects using uniform external forces match the mechanics of existing games and puzzles, such as Mega Maze, 2048 and Labyrinth, and have also been investigated in the context of self-assembly, programmable matter and robotic motion planning. The problem of obtaining a given shape from a starting configuration is know to be NP-complete. We show that, for every n, there are sparse initial configurations of n tokens (i.e., where no two tokens are in the same row or column) that can be compacted into any a×b box such that ab = n. However, only 1×k, 2×k and 3×3 boxes are obtainable from any arbitrary sparse configuration with a matching number of tokens. We also study the problem of rearranging labeled tokens into a configuration of the same shape, but with permuted tokens. For every initial configuration of the tokens, we provide a complete characterization of what other configurations can be obtained by means of line pushes.
Cite as

Hugo A. Akitaya, Maarten Löffler, and Giovanni Viglietta. Pushing Blocks by Sweeping Lines. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.FUN.2022.1,
  author =	{A. Akitaya, Hugo and L\"{o}ffler, Maarten and Viglietta, Giovanni},
  title =	{{Pushing Blocks by Sweeping Lines}},
  booktitle =	{11th International Conference on Fun with Algorithms (FUN 2022)},
  pages =	{1:1--1:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-232-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{226},
  editor =	{Fraigniaud, Pierre and Uno, Yushi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.1},
  URN =		{urn:nbn:de:0030-drops-159719},
  doi =		{10.4230/LIPIcs.FUN.2022.1},
  annote =	{Keywords: Reconfiguration, Global Control, Pushing Blocks, Permutation}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.10
Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds

Authors: Ankush Acharyya, Ramesh K. Jallu, Maarten Löffler, Gert G.T. Meijer, Maria Saumell, Rodrigo I. Silveira, and Frank Staals

Published in: LIPIcs, Volume 208, 11th International Conference on Geographic Information Science (GIScience 2021) - Part II

Abstract
An important task in terrain analysis is computing viewsheds. A viewshed is the union of all the parts of the terrain that are visible from a given viewpoint or set of viewpoints. The complexity of a viewshed can vary significantly depending on the terrain topography and the viewpoint position. In this work we study a new topographic attribute, the prickliness, that measures the number of local maxima in a terrain from all possible angles of view. We show that the prickliness effectively captures the potential of terrains to have high complexity viewsheds. We present near-optimal algorithms to compute it for TIN terrains, and efficient approximate algorithms for raster DEMs. We validate the usefulness of the prickliness attribute with experiments in a large set of real terrains.
Cite as

Ankush Acharyya, Ramesh K. Jallu, Maarten Löffler, Gert G.T. Meijer, Maria Saumell, Rodrigo I. Silveira, and Frank Staals. Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{acharyya_et_al:LIPIcs.GIScience.2021.II.10,
  author =	{Acharyya, Ankush and Jallu, Ramesh K. and L\"{o}ffler, Maarten and Meijer, Gert G.T. and Saumell, Maria and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Terrain Prickliness: Theoretical Grounds for High Complexity Viewsheds}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.II.10},
  URN =		{urn:nbn:de:0030-drops-147697},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.10},
  annote =	{Keywords: Digital elevation model, Triangulated irregular network, Viewshed complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.26
Uncertain Curve Simplification

Authors: Kevin Buchin, Maarten Löffler, Aleksandr Popov, and Marcel Roeloffzen

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We study the problem of polygonal curve simplification under uncertainty, where instead of a sequence of exact points, each uncertain point is represented by a region which contains the (unknown) true location of the vertex. The regions we consider are disks, line segments, convex polygons, and discrete sets of points. We are interested in finding the shortest subsequence of uncertain points such that no matter what the true location of each uncertain point is, the resulting polygonal curve is a valid simplification of the original polygonal curve under the Hausdorff or the Fréchet distance. For both these distance measures, we present polynomial-time algorithms for this problem.
Cite as

Kevin Buchin, Maarten Löffler, Aleksandr Popov, and Marcel Roeloffzen. Uncertain Curve Simplification. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.MFCS.2021.26,
  author =	{Buchin, Kevin and L\"{o}ffler, Maarten and Popov, Aleksandr and Roeloffzen, Marcel},
  title =	{{Uncertain Curve Simplification}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.26},
  URN =		{urn:nbn:de:0030-drops-144666},
  doi =		{10.4230/LIPIcs.MFCS.2021.26},
  annote =	{Keywords: Curves, Uncertainty, Simplification, Fr\'{e}chet Distance, Hausdorff Distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.5
Chasing Puppies: Mobile Beacon Routing on Closed Curves

Authors: Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others’ work on beacon-based routing. Consider a human and a puppy on a simple closed curve in the plane. The human can walk along the curve at bounded speed and change direction as desired. The puppy runs with unbounded speed along the curve as long as the Euclidean straight-line distance to the human is decreasing, so that it is always at a point on the curve where the distance is locally minimal. Assuming that the curve is smooth (with some mild genericity constraints) or a simple polygon, we prove that the human can always catch the puppy in finite time.
Cite as

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi Vermeulen, and Giovanni Viglietta. Chasing Puppies: Mobile Beacon Routing on Closed Curves. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 5:1-5:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2021.5,
  author =	{Abrahamsen, Mikkel and Erickson, Jeff and Kostitsyna, Irina and L\"{o}ffler, Maarten and Miltzow, Tillmann and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi and Viglietta, Giovanni},
  title =	{{Chasing Puppies: Mobile Beacon Routing on Closed Curves}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{5:1--5:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.5},
  URN =		{urn:nbn:de:0030-drops-138046},
  doi =		{10.4230/LIPIcs.SoCG.2021.5},
  annote =	{Keywords: Beacon routing, navigation, generic smooth curves, puppies}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.11
Adjacency Graphs of Polyhedral Surfaces

Authors: Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Cite as

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11,
  author =	{Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
  title =	{{Adjacency Graphs of Polyhedral Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.11},
  URN =		{urn:nbn:de:0030-drops-138107},
  doi =		{10.4230/LIPIcs.SoCG.2021.11},
  annote =	{Keywords: polyhedral complexes, realizability, contact representation}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.20
Fréchet Distance for Uncertain Curves

Authors: Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
In this paper we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. We define an uncertain curve as a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the continuous Fréchet distance, and the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound discrete Fréchet distance can be computed in polynomial time using dynamic programming. Furthermore, we show that computing the expected discrete or continuous Fréchet distance is #P-hard when the uncertainty regions are modelled as point sets or line segments. On the positive side, we argue that in any constant dimension there is a FPTAS for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We then argue there is a near-linear-time 3-approximation for the decision problem when the regions are convex and roughly δ-separated. Finally, we study the setting with Sakoe - Chiba bands, restricting the alignment of the two curves, and give polynomial-time algorithms for upper bound and expected (discrete) Fréchet distance for point-set-modelled uncertainty regions.
Cite as

Kevin Buchin, Chenglin Fan, Maarten Löffler, Aleksandr Popov, Benjamin Raichel, and Marcel Roeloffzen. Fréchet Distance for Uncertain Curves. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 20:1-20:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2020.20,
  author =	{Buchin, Kevin and Fan, Chenglin and L\"{o}ffler, Maarten and Popov, Aleksandr and Raichel, Benjamin and Roeloffzen, Marcel},
  title =	{{Fr\'{e}chet Distance for Uncertain Curves}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{20:1--20:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.20},
  URN =		{urn:nbn:de:0030-drops-124276},
  doi =		{10.4230/LIPIcs.ICALP.2020.20},
  annote =	{Keywords: Curves, Uncertainty, Fr\'{e}chet Distance, Hardness}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.23
Trajectory Visibility

Authors: Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We study the problem of testing whether there exists a time at which two entities moving along different piece-wise linear trajectories among polygonal obstacles are mutually visible. We study several variants, depending on whether or not the obstacles form a simple polygon, trajectories may intersect the polygon edges, and both or only one of the entities are moving. For constant complexity trajectories contained in a simple polygon with n vertices, we provide an 𝒪(n) time algorithm to test if there is a time at which the entities can see each other. If the polygon contains holes, we present an 𝒪(n log n) algorithm. We show that this is tight. We then consider storing the obstacles in a data structure, such that queries consisting of two line segments can be efficiently answered. We show that for all variants it is possible to answer queries in sublinear time using polynomial space and preprocessing time. As a critical intermediate step, we provide an efficient solution to a problem of independent interest: preprocess a convex polygon such that we can efficiently test intersection with a quadratic curve segment. If the obstacles form a simple polygon, this allows us to answer visibility queries in 𝒪(n³/4log³ n) time using 𝒪(nlog⁵ n) space. For more general obstacles the query time is 𝒪(log^k n), for a constant but large value k, using 𝒪(n^{3k}) space. We provide more efficient solutions when one of the entities remains stationary.
Cite as

Patrick Eades, Ivor van der Hoog, Maarten Löffler, and Frank Staals. Trajectory Visibility. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{eades_et_al:LIPIcs.SWAT.2020.23,
  author =	{Eades, Patrick and van der Hoog, Ivor and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Trajectory Visibility}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{23:1--23:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.23},
  URN =		{urn:nbn:de:0030-drops-122701},
  doi =		{10.4230/LIPIcs.SWAT.2020.23},
  annote =	{Keywords: trajectories, visibility, data structures, semi-algebraic range searching}
}
Document
DOI: 10.4230/DagRep.9.8.84
Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)

Authors: Maarten Löffler, Anna Lubiw, Saul Schleimer, and Erin Moriarty Wolf Chambers

Published in: Dagstuhl Reports, Volume 9, Issue 8 (2020)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19352 ``Computation in Low-Dimensional Geometry and Topology''. The seminar participants investigated problems in: knot theory, trajectory analysis, algorithmic topology, computational geometry of curves, and graph drawing, with an emphasis on how low-dimensional structures change over time.
Cite as

Maarten Löffler, Anna Lubiw, Saul Schleimer, and Erin Moriarty Wolf Chambers. Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352). In Dagstuhl Reports, Volume 9, Issue 8, pp. 84-112, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{loffler_et_al:DagRep.9.8.84,
  author =	{L\"{o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Wolf Chambers, Erin Moriarty},
  title =	{{Computation in Low-Dimensional Geometry and Topology (Dagstuhl Seminar 19352)}},
  pages =	{84--112},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{8},
  editor =	{L\"{o}ffler, Maarten and Lubiw, Anna and Schleimer, Saul and Wolf Chambers, Erin Moriarty},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.9.8.84},
  URN =		{urn:nbn:de:0030-drops-117734},
  doi =		{10.4230/DagRep.9.8.84},
  annote =	{Keywords: Geometric topology, Graph Drawing, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.67
Global Curve Simplification

Authors: Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

Abstract
Due to its many applications, curve simplification is a long-studied problem in computational geometry and adjacent disciplines, such as graphics, geographical information science, etc. Given a polygonal curve P with n vertices, the goal is to find another polygonal curve P' with a smaller number of vertices such that P' is sufficiently similar to P. Quality guarantees of a simplification are usually given in a local sense, bounding the distance between a shortcut and its corresponding section of the curve. In this work we aim to provide a systematic overview of curve simplification problems under global distance measures that bound the distance between P and P'. We consider six different curve distance measures: three variants of the Hausdorff distance and three variants of the Fréchet distance. And we study different restrictions on the choice of vertices for P'. We provide polynomial-time algorithms for some variants of the global curve simplification problem, and show NP-hardness for other variants. Through this systematic study we observe, for the first time, some surprising patterns, and suggest directions for future research in this important area.
Cite as

Mees van de Kerkhof, Irina Kostitsyna, Maarten Löffler, Majid Mirzanezhad, and Carola Wenk. Global Curve Simplification. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vandekerkhof_et_al:LIPIcs.ESA.2019.67,
  author =	{van de Kerkhof, Mees and Kostitsyna, Irina and L\"{o}ffler, Maarten and Mirzanezhad, Majid and Wenk, Carola},
  title =	{{Global Curve Simplification}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{67:1--67:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.67},
  URN =		{urn:nbn:de:0030-drops-111887},
  doi =		{10.4230/LIPIcs.ESA.2019.67},
  annote =	{Keywords: Curve simplification, Fr\'{e}chet distance, Hausdorff distance}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2019.9
Geometric Multicut

Authors: Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
We study the following separation problem: Given a collection of colored objects in the plane, compute a shortest "fence" F, i.e., a union of curves of minimum total length, that separates every two objects of different colors. Two objects are separated if F contains a simple closed curve that has one object in the interior and the other in the exterior. We refer to the problem as GEOMETRIC k-CUT, where k is the number of different colors, as it can be seen as a geometric analogue to the well-studied multicut problem on graphs. We first give an O(n^4 log^3 n)-time algorithm that computes an optimal fence for the case where the input consists of polygons of two colors and n corners in total. We then show that the problem is NP-hard for the case of three colors. Finally, we give a (2-4/3k)-approximation algorithm.
Cite as

Mikkel Abrahamsen, Panos Giannopoulos, Maarten Löffler, and Günter Rote. Geometric Multicut. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.ICALP.2019.9,
  author =	{Abrahamsen, Mikkel and Giannopoulos, Panos and L\"{o}ffler, Maarten and Rote, G\"{u}nter},
  title =	{{Geometric Multicut}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.9},
  URN =		{urn:nbn:de:0030-drops-105850},
  doi =		{10.4230/LIPIcs.ICALP.2019.9},
  annote =	{Keywords: multicut, clustering, Steiner tree}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.42
Preprocessing Ambiguous Imprecise Points

Authors: Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
Let R = {R_1, R_2, ..., R_n} be a set of regions and let X = {x_1, x_2, ..., x_n} be an (unknown) point set with x_i in R_i. Region R_i represents the uncertainty region of x_i. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in R? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to R followed by a reconstruction phase during which a desired structure on X is computed. Recent results in this model parametrize the reconstruction time by the ply of R, which is the maximum overlap between the regions in R. We introduce the ambiguity A(R) as a more fine-grained measure of the degree of overlap in R. We show how to preprocess a set of d-dimensional disks in O(n log n) time such that we can sort X (if d=1) and reconstruct a quadtree on X (if d >= 1 but constant) in O(A(R)) time. If A(R) is sub-linear, then reporting the result dominates the running time of the reconstruction phase. However, we can still return a suitable data structure representing the result in O(A(R)) time. In one dimension, {R} is a set of intervals and the ambiguity is linked to interval entropy, which in turn relates to the well-studied problem of sorting under partial information. The number of comparisons necessary to find the linear order underlying a poset P is lower-bounded by the graph entropy of P. We show that if P is an interval order, then the ambiguity provides a constant-factor approximation of the graph entropy. This gives a lower bound of Omega(A(R)) in all dimensions for the reconstruction phase (sorting or any proximity structure), independent of any preprocessing; hence our result is tight. Finally, our results imply that one can approximate the entropy of interval graphs in O(n log n) time, improving the O(n^{2.5}) bound by Cardinal et al.
Cite as

Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, and Bettina Speckmann. Preprocessing Ambiguous Imprecise Points. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 42:1-42:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2019.42,
  author =	{van der Hoog, Ivor and Kostitsyna, Irina and L\"{o}ffler, Maarten and Speckmann, Bettina},
  title =	{{Preprocessing Ambiguous Imprecise Points}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{42:1--42:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.42},
  URN =		{urn:nbn:de:0030-drops-104460},
  doi =		{10.4230/LIPIcs.SoCG.2019.42},
  annote =	{Keywords: preprocessing, imprecise points, entropy, sorting, proximity structures}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2019.65
A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition)

Authors: Maarten Löffler

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We have verified experimentally that there is at least one point set on which Andrew’s algorithm (based on Graham’s scan) to compute the convex hull of a set of points in the plane is significantly faster than a brute-force approach, thus supporting existing theoretical analysis with practical evidence. Specifically, we determined that executing Andrew’s algorithm on the point set P = {(1,4), (2,8), (3,10), (4,1), (5,7), (6,3), (7,9), (8,5), (9,2), (10,6)} takes 41 minutes and 18 seconds; the brute-force approach takes 3 hours, 49 minutes, and 5 seconds.
Cite as

Maarten Löffler. A Manual Comparison of Convex Hull Algorithms (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 65:1-65:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{loffler:LIPIcs.SoCG.2019.65,
  author =	{L\"{o}ffler, Maarten},
  title =	{{A Manual Comparison of Convex Hull Algorithms}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{65:1--65:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.65},
  URN =		{urn:nbn:de:0030-drops-104690},
  doi =		{10.4230/LIPIcs.SoCG.2019.65},
  annote =	{Keywords: convex hull, efficiency}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2018.52
Convex Partial Transversals of Planar Regions

Authors: Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma

Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Abstract
We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.
Cite as

Vahideh Keikha, Mees van de Kerkhof, Marc van Kreveld, Irina Kostitsyna, Maarten Löffler, Frank Staals, Jérôme Urhausen, Jordi L. Vermeulen, and Lionov Wiratma. Convex Partial Transversals of Planar Regions. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 52:1-52:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{keikha_et_al:LIPIcs.ISAAC.2018.52,
  author =	{Keikha, Vahideh and van de Kerkhof, Mees and van Kreveld, Marc and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank and Urhausen, J\'{e}r\^{o}me and Vermeulen, Jordi L. and Wiratma, Lionov},
  title =	{{Convex Partial Transversals of Planar Regions}},
  booktitle =	{29th International Symposium on Algorithms and Computation (ISAAC 2018)},
  pages =	{52:1--52:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.52},
  URN =		{urn:nbn:de:0030-drops-100003},
  doi =		{10.4230/LIPIcs.ISAAC.2018.52},
  annote =	{Keywords: computational geometry, algorithms, NP-hardness, convex transversals}
}
Document
Short Paper
DOI: 10.4230/LIPIcs.GISCIENCE.2018.64
An Experimental Comparison of Two Definitions for Groups of Moving Entities (Short Paper)

Authors: Lionov Wiratma, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 114, 10th International Conference on Geographic Information Science (GIScience 2018)

Abstract
Two of the grouping definitions for trajectories that have been developed in recent years allow a continuous motion model and allow varying shape groups. One of these definitions was suggested as a refinement of the other. In this paper we perform an experimental comparison to highlight the differences in these two definitions on various data sets.
Cite as

Lionov Wiratma, Maarten Löffler, and Frank Staals. An Experimental Comparison of Two Definitions for Groups of Moving Entities (Short Paper). In 10th International Conference on Geographic Information Science (GIScience 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 114, pp. 64:1-64:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{wiratma_et_al:LIPIcs.GISCIENCE.2018.64,
  author =	{Wiratma, Lionov and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{An Experimental Comparison of Two Definitions for Groups of Moving Entities}},
  booktitle =	{10th International Conference on Geographic Information Science (GIScience 2018)},
  pages =	{64:1--64:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-083-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{114},
  editor =	{Winter, Stephan and Griffin, Amy and Sester, Monika},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.GISCIENCE.2018.64},
  URN =		{urn:nbn:de:0030-drops-93928},
  doi =		{10.4230/LIPIcs.GISCIENCE.2018.64},
  annote =	{Keywords: Trajectories, grouping algorithms, experimental comparison}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.45
Dynamic Smooth Compressed Quadtrees

Authors: Ivor van der Hoog, Elena Khramtcova, and Maarten Löffler

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We introduce dynamic smooth (a.k.a. balanced) compressed quadtrees with worst-case constant time updates in constant dimensions. We distinguish two versions of the problem. First, we show that quadtrees as a space-division data structure can be made smooth and dynamic subject to split and merge operations on the quadtree cells. Second, we show that quadtrees used to store a set of points in R^d can be made smooth and dynamic subject to insertions and deletions of points. The second version uses the first but must additionally deal with compression and alignment of quadtree components. In both cases our updates take 2^{O(d log d)} time, except for the point location part in the second version which has a lower bound of Omega(log n); but if a pointer (finger) to the correct quadtree cell is given, the rest of the updates take worst-case constant time. Our result implies that several classic and recent results (ranging from ray tracing to planar point location) in computational geometry which use quadtrees can deal with arbitrary point sets on a real RAM pointer machine.
Cite as

Ivor van der Hoog, Elena Khramtcova, and Maarten Löffler. Dynamic Smooth Compressed Quadtrees. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 45:1-45:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vanderhoog_et_al:LIPIcs.SoCG.2018.45,
  author =	{van der Hoog, Ivor and Khramtcova, Elena and L\"{o}ffler, Maarten},
  title =	{{Dynamic Smooth Compressed Quadtrees}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{45:1--45:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.45},
  URN =		{urn:nbn:de:0030-drops-87581},
  doi =		{10.4230/LIPIcs.SoCG.2018.45},
  annote =	{Keywords: smooth, dynamic, data structure, quadtree, compression, alignment, Real RAM}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.56
On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance

Authors: Marc van Kreveld, Maarten Löffler, and Lionov Wiratma

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon. We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification.
Cite as

Marc van Kreveld, Maarten Löffler, and Lionov Wiratma. On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 56:1-56:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.SoCG.2018.56,
  author =	{van Kreveld, Marc and L\"{o}ffler, Maarten and Wiratma, Lionov},
  title =	{{On Optimal Polyline Simplification Using the Hausdorff and Fr\'{e}chet Distance}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{56:1--56:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.56},
  URN =		{urn:nbn:de:0030-drops-87694},
  doi =		{10.4230/LIPIcs.SoCG.2018.56},
  annote =	{Keywords: polygonal line simplification, Hausdorff distance, Fr\'{e}chet distance, Imai-Iri, Douglas-Peucker}
}
Document
DOI: 10.4230/DagRep.7.2.64
Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072)

Authors: Benjamin Burton, Maarten Löffler, Carola Wenk, and Erin Moriarty Wolf Chambers

Published in: Dagstuhl Reports, Volume 7, Issue 2 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17072 "Applications of Topology to the Analysis of 1-Dimensional Objects".
Cite as

Benjamin Burton, Maarten Löffler, Carola Wenk, and Erin Moriarty Wolf Chambers. Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072). In Dagstuhl Reports, Volume 7, Issue 2, pp. 64-88, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{burton_et_al:DagRep.7.2.64,
  author =	{Burton, Benjamin and L\"{o}ffler, Maarten and Wenk, Carola and Wolf Chambers, Erin Moriarty},
  title =	{{Applications of Topology to the Analysis of 1-Dimensional Objects (Dagstuhl Seminar 17072)}},
  pages =	{64--88},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{2},
  editor =	{Burton, Benjamin and L\"{o}ffler, Maarten and Wenk, Carola and Wolf Chambers, Erin Moriarty},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.7.2.64},
  URN =		{urn:nbn:de:0030-drops-73536},
  doi =		{10.4230/DagRep.7.2.64},
  annote =	{Keywords: curves, graph drawing, homotopy, knot theory}
}
Document
Multimedia Contribution
DOI: 10.4230/LIPIcs.SoCG.2017.64
Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution)

Authors: Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
By folding the free-space diagram for efficient preprocessing, we show that the Frechet distance between 1D curves can be computed in O(nk log n) time, assuming one curve has ply k.
Cite as

Kevin Buchin, Jinhee Chun, Maarten Löffler, Aleksandar Markovic, Wouter Meulemans, Yoshio Okamoto, and Taichi Shiitada. Folding Free-Space Diagrams: Computing the Fréchet Distance between 1-Dimensional Curves (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 64:1-64:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2017.64,
  author =	{Buchin, Kevin and Chun, Jinhee and L\"{o}ffler, Maarten and Markovic, Aleksandar and Meulemans, Wouter and Okamoto, Yoshio and Shiitada, Taichi},
  title =	{{Folding Free-Space Diagrams: Computing the Fr\'{e}chet Distance between 1-Dimensional Curves}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{64:1--64:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.64},
  URN =		{urn:nbn:de:0030-drops-72417},
  doi =		{10.4230/LIPIcs.SoCG.2017.64},
  annote =	{Keywords: Frechet distance, ply, k-packed curves}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.48
A Refined Definition for Groups of Moving Entities and its Computation

Authors: Marc van Kreveld, Maarten Löffler, Frank Staals, and Lionov Wiratma

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al. [JoCG, 2015] introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R^1, specified by linear interpolation in a sequence of tau time stamps, we show that all maximal groups can be computed in O(tau^2 n^4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of alpha(n) in the running time. In higher dimensions, we can compute all maximal groups in O(tau^2 n^5 log n) time (for any constant number of dimensions). We also show that one tau factor can be traded for a much higher dependence on n by giving a O(tau n^4 2^n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on n and linear dependence on tau.
Cite as

Marc van Kreveld, Maarten Löffler, Frank Staals, and Lionov Wiratma. A Refined Definition for Groups of Moving Entities and its Computation. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 48:1-48:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.ISAAC.2016.48,
  author =	{van Kreveld, Marc and L\"{o}ffler, Maarten and Staals, Frank and Wiratma, Lionov},
  title =	{{A Refined Definition for Groups of Moving Entities and its Computation}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{48:1--48:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.48},
  URN =		{urn:nbn:de:0030-drops-68188},
  doi =		{10.4230/LIPIcs.ISAAC.2016.48},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.27
Homotopy Measures for Representative Trajectories

Authors: Erin Chambers, Irina Kostitsyna, Maarten Löffler, and Frank Staals

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
An important task in trajectory analysis is defining a meaningful representative for a cluster of similar trajectories. Formally defining and computing such a representative r is a challenging problem. We propose and discuss two new definitions, both of which use only the geometry of the input trajectories. The definitions are based on the homotopy area as a measure of similarity between two curves, which is a minimum area swept by all possible deformations of one curve into the other. In the first definition we wish to minimize the maximum homotopy area between r and any input trajectory, whereas in the second definition we wish to minimize the sum of the homotopy areas between r and the input trajectories. For both definitions computing an optimal representative is NP-hard. However, for the case of minimizing the sum of the homotopy areas, an optimal representative can be found efficiently in a natural class of restricted inputs, namely, when the arrangement of trajectories forms a directed acyclic graph.
Cite as

Erin Chambers, Irina Kostitsyna, Maarten Löffler, and Frank Staals. Homotopy Measures for Representative Trajectories. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.ESA.2016.27,
  author =	{Chambers, Erin and Kostitsyna, Irina and L\"{o}ffler, Maarten and Staals, Frank},
  title =	{{Homotopy Measures for Representative Trajectories}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.27},
  URN =		{urn:nbn:de:0030-drops-63783},
  doi =		{10.4230/LIPIcs.ESA.2016.27},
  annote =	{Keywords: trajectory analysis, representative trajectory, homotopy area}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.49
On the Complexity of Minimum-Link Path Problems

Authors: Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We revisit the minimum-link path problem: Given a polyhedral domain and two points in it, connect the points by a polygonal path with minimum number of edges. We consider settings where the min-link path's vertices or edges can be restricted to lie on the boundary of the domain, or can be in its interior. Our results include bit complexity bounds, a novel general hardness construction, and a polynomial-time approximation scheme. We fully characterize the situation in 2D, and provide first results in dimensions 3 and higher for several versions of the problem. Concretely, our results resolve several open problems. We prove that computing the minimum-link diffuse reflection path, motivated by ray tracing in computer graphics, is NP-hard, even for two-dimensional polygonal domains with holes. This has remained an open problem [Ghosh et al. 2012] despite a large body of work on the topic. We also resolve the open problem from [Mitchell et al. 1992] mentioned in the handbook [Goodman and O'Rourke, 2004] (see Chapter 27.5, Open problem 3) and The Open Problems Project [Demaine et al. TOPP] (see Problem 22): "What is the complexity of the minimum-link path problem in 3-space?" Our results imply that the problem is NP-hard even on terrains (and hence, due to discreteness of the answer, there is no FPTAS unless P=NP), but admits a PTAS.
Cite as

Irina Kostitsyna, Maarten Löffler, Valentin Polishchuk, and Frank Staals. On the Complexity of Minimum-Link Path Problems. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 49:1-49:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2016.49,
  author =	{Kostitsyna, Irina and L\"{o}ffler, Maarten and Polishchuk, Valentin and Staals, Frank},
  title =	{{On the Complexity of Minimum-Link Path Problems}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{49:1--49:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.49},
  URN =		{urn:nbn:de:0030-drops-59412},
  doi =		{10.4230/LIPIcs.SoCG.2016.49},
  annote =	{Keywords: minimum-linkpath, diffuse reflection, terrain, bit complexity, NP-hardness}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.61
Grouping Time-Varying Data for Interactive Exploration

Authors: Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.
Cite as

Arthur van Goethem, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Grouping Time-Varying Data for Interactive Exploration. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 61:1-61:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{vangoethem_et_al:LIPIcs.SoCG.2016.61,
  author =	{van Goethem, Arthur and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Grouping Time-Varying Data for Interactive Exploration}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{61:1--61:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.61},
  URN =		{urn:nbn:de:0030-drops-59539},
  doi =		{10.4230/LIPIcs.SoCG.2016.61},
  annote =	{Keywords: Trajectory, Time series, Moving entity, Grouping, Algorithm, Data structure}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.16
Recognizing a DOG is Hard, But Not When It is Thin and Unit

Authors: William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
We define the notion of disk-obedience for a set of disks in the plane and give results for diskobedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.
Cite as

William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk. Recognizing a DOG is Hard, But Not When It is Thin and Unit. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{evans_et_al:LIPIcs.FUN.2016.16,
  author =	{Evans, William and van Garderen, Mereke and L\"{o}ffler, Maarten and Polishchuk, Valentin},
  title =	{{Recognizing a DOG is Hard, But Not When It is Thin and Unit}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{16:1--16:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.16},
  URN =		{urn:nbn:de:0030-drops-58671},
  doi =		{10.4230/LIPIcs.FUN.2016.16},
  annote =	{Keywords: graph drawing, planar graphs, disk intersection graphs}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.674
Trajectory Grouping Structure under Geodesic Distance

Authors: Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure. Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly epsilon, where epsilon is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with tau vertices each we give an O(tau n^2) upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an O(tau(n^2 + m lambda_4(n))) upper bound, where m is the total complexity of the obstacles, and lambda_s(n) denotes the maximum length of a Davenport-Schinzel sequence of n symbols of order s. In case of general obstacles we give an O(tau min(n^2 + m^3 lambda_4(n), n^2m^2)) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.
Cite as

Irina Kostitsyna, Marc van Kreveld, Maarten Löffler, Bettina Speckmann, and Frank Staals. Trajectory Grouping Structure under Geodesic Distance. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 674-688, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SOCG.2015.674,
  author =	{Kostitsyna, Irina and van Kreveld, Marc and L\"{o}ffler, Maarten and Speckmann, Bettina and Staals, Frank},
  title =	{{Trajectory Grouping Structure under Geodesic Distance}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{674--688},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.674},
  URN =		{urn:nbn:de:0030-drops-51212},
  doi =		{10.4230/LIPIcs.SOCG.2015.674},
  annote =	{Keywords: moving entities, trajectories, grouping, computational geometry}
}
Document
DOI: 10.4230/DagSemProc.10441.2
Listing all maximal cliques in sparse graphs in near-optimal time

Authors: David Eppstein, Maarten Löffler, and Darren Strash

Published in: Dagstuhl Seminar Proceedings, Volume 10441, Exact Complexity of NP-hard Problems (2011)

Abstract
The degeneracy of an $n$-vertex graph $G$ is the smallest number $d$ such that every subgraph of $G$ contains a vertex of degree at most $d$. We show that there exists a nearly-optimal fixed-parameter tractable algorithm for enumerating all maximal cliques, parametrized by degeneracy. To achieve this result, we modify the classic Bron--Kerbosch algorithm and show that it runs in time $O(dn3^{d/3})$. We also provide matching upper and lower bounds showing that the largest possible number of maximal cliques in an $n$-vertex graph with degeneracy $d$ (when $d$ is a multiple of 3 and $nge d+3$) is $(n-d)3^{d/3}$. Therefore, our algorithm matches the $Theta(d(n-d)3^{d/3})$ worst-case output size of the problem whenever $n-d=Omega(n)$.
Cite as

David Eppstein, Maarten Löffler, and Darren Strash. Listing all maximal cliques in sparse graphs in near-optimal time. In Exact Complexity of NP-hard Problems. Dagstuhl Seminar Proceedings, Volume 10441, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{eppstein_et_al:DagSemProc.10441.2,
  author =	{Eppstein, David and L\"{o}ffler, Maarten and Strash, Darren},
  title =	{{Listing all maximal cliques in sparse graphs in near-optimal time}},
  booktitle =	{Exact Complexity of NP-hard Problems},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10441},
  editor =	{Thore Husfeldt and Dieter Kratsch and Ramamohan Paturi and Gregory B. Sorkin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10441.2},
  URN =		{urn:nbn:de:0030-drops-29356},
  doi =		{10.4230/DagSemProc.10441.2},
  annote =	{Keywords: Clique, backtracking, degeneracy, worst-case optimality}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact